package com.mdnote.practice.linked_list;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/18
 * @description 删除链表的倒数第N个节点
 */
public class LeetCode19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 双指针完成，先让指针1走n + 1 指针2指向0，同时往前走，指针1到头了就删除指针2的下一个节点
        // 鲁棒性： 1. 输入的head是null，输入的n是0
        //         2. 链表长度不到n，直接返回head

        if (head == null || n <= 0) {
            return head;
        }
        ListNode fast = head, slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
            if (fast == null) {
                return head.next;
            }
        }

        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // remove slow
        slow.next = slow.next.next;
        return head;
    }

      public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
}
